package problems.contest;

import java.util.*;

/**
 * @author habitplus
 * @since 2022/8/6 22:24
 */
public class BCT84 {
    /**
     * T1
     */
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
//        HashMap<Integer, Integer> map = new HashMap<>();
        TreeMap<Integer, Integer> map = new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });

        for (int[] it : items1) {
            map.put(it[0], it[1]);
        }

        for (int[] it : items2) {
            if (map.containsKey(it[0])) {
                map.put(it[0], map.get(it[0]) + it[1]);
            } else {
                map.put(it[0], it[1]);
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            List<Integer> tmpList = new ArrayList<>();
            tmpList.add(e.getKey());
            tmpList.add(e.getValue());
            ans.add(tmpList);
        }
        return ans;
    }


    /**
     * T2
     */
    public long countBadPairs(int[] nums) {
        if (nums == null || nums.length < 2) return 0;

        int n = nums.length;
        long ans = 0;
        // num[i] - i 的个数
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 1);
        for (int i = 1; i < n; ++i) {
            int cnt = map.getOrDefault(nums[i] - i, 0);
            ans += i - cnt;
            map.put(nums[i] - i, cnt + 1);
        }

        return ans;
    }


    /**
     * T3
     */
    public long taskSchedulerII(int[] tasks, int space) {
        int n = tasks.length;
        // 记录当前任务在第几天执行
        HashMap<Integer, Long> map = new HashMap<>();

        long day = 1;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(tasks[i])) {
                long last = map.get(tasks[i]);
                if (day - last <= space) {
                    // 不能执行当前任务，得休息
                    map.put(tasks[i], last + space + 1);
                    day += (last +space + 2 - day);
                } else {
                    map.put(tasks[i], day);
                    day++;
                }
            } else {
                // 直接完成
                map.put(tasks[i], day);
                day++;
            }
        }

        return day - 1;
    }
}
